package com.LeetCode.dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * 地下城游戏 骑士救公主
 */
public class UnderGroundGame {

    int[][] mono;

    public int calculateMinimumHP(int[][] dungeon) {
        int n = dungeon.length;
        int m = dungeon[0].length;
        mono = new int[n][m];
        return dfs(dungeon,n,m,0,0);
    }

    public int dfs(int[][] dungeon, int n, int m, int i, int j){
        if(i == n-1 && j == m-1)
            return Math.max(1, 1 - dungeon[i][j]);

        if(mono[i][j] > 0)
            return mono[i][j];

        int minRes = 0;

        if( i == n-1)
            minRes =  Math.max(dfs(dungeon,n,m,i,j+1) - dungeon[i][j] , 1);

        else if( j == m-1)
            minRes = Math.max(dfs(dungeon,n,m,i+1,j) - dungeon[i][j] , 1);

        else
            minRes = Math.max(Math.min(dfs(dungeon,n,m,i+1,j),
                    dfs(dungeon,n,m,i,j+1)) - dungeon[i][j],1);

        return mono[i][j] = minRes;
    }





    @Test
    public void test(){
        int[][] dungeon = {
                {-2,-3,3},
                {-5,-10,1},
                {10,30,-5}
        };
        System.out.println(calculateMinimumHP(dungeon));
    }
}
